package com.atguigu.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
* 逆波兰表达式
* */
public class PolandNation {
    public static void main(String[] args) {
        //逆波兰表达式
        //（3+4）*5-6=> 3 4 + 5 * 6 -，使用空格隔开
        String str="3 4 + 5 * 6 -";
        //1。将str放入到ArrayList中
        List<String> listString = getListString(str);
        System.out.println(listString);
        //2.将ArrayList传递给一个方法，遍历Arraylist配合栈完成计算
        int res = getPolandNationRes(listString);
        System.out.println("res = " + res);


        System.out.println("中缀转后缀");
        String z="1+((2+3)*4)-5";
        List<String> strings = toInfixExperssionList(z);
        System.out.println("strings = " + strings);
        List<String> strings1 = parseSuffixExpreesionList(strings);
        System.out.println("strings1 = " + strings1);
        int res1 = getPolandNationRes(strings1);
        System.out.println("res1 = " + res1);

    }
    //将一逆波兰表达式，依次将数据和符号放入到ArrayList
    public static List<String> getListString(String str){
        String[] strArr=str.split(" ");
        List<String> list=new ArrayList<>();
        for (String str_index:strArr) {
            list.add(str_index);
        }
        return list;
    }
    //完成对逆波兰表达式的计算
    /*
    * 逆波兰表达式
    * 设计一个栈
    * 遇到数就加入栈
    * 遇到符号就，pop出最上面的两个数运算
    * 然后进栈，
    * 最后留在栈中的数字就是最后的结果了
    *
    * */
    public static int getPolandNationRes(List<String> strings){
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < strings.size(); i++) {
            //使用正则表达式计算,看看是不是数字
            if(strings.get(i).matches("\\d+")){
                //入栈
                stack.push(strings.get(i));
            }else{
                //pop出两个数，并运算入栈
                int num2=Integer.parseInt(stack.pop());
                int num1=Integer.parseInt(stack.pop());
                int res=0;
                if(strings.get(i).equals("+")){
                    res=num1+num2;
                }else if(strings.get(i).equals("-")){
                    res=num1-num2;
                }else if(strings.get(i).equals("*")){
                    res=num1*num2;
                }else{
                    res=num1/num2;
                }
                stack.push(res+"");
            }
        }
        //最后留在栈中的就是结果了
        return Integer.parseInt(stack.pop());
    }

    //完成中缀表达式转后缀表达式
    //1.1+((2+3)*4)-5
    //2.因为对字符串计算不方便，因此将str装换为List
    //3.将中缀表达式对应的List转换成后缀表达式List
    //将Str转换成List
    public static List<String> toInfixExperssionList(String s){
        //
        List<String> ls=new ArrayList<>();
        int i=0;//这是一个指针，用于遍历字符串
        String str="";
        while (i<s.length()){
            if(s.charAt(i)<48||s.charAt(i)>57){
                //如果不是数字，直接输入ls
                ls.add(s.charAt(i)+"");
                i++;
            }else{
                //数组的话要注意是不是非单位数
                str="";
                while (i<s.length()&&(s.charAt(i)>=48&&s.charAt(i)<=57)){
                    str=str+s.charAt(i);
                    i++;
                }
                ls.add(str);
            }
        }
        return ls;
    }
    //中中缀表达式的List转换成后缀表达式的List
    /*
     * 1初始化两个栈，运算符栈s1,和存储中间结果的栈s2
     * 2从左至右扫描中缀表达式
     * 3遇到操作数，将其压入s2
     * 4遇到运算符号，比较其与s1栈顶运算符的优先级
     *   4-1如果s1为空，或者栈顶运算符为“(”,则直接将此运算符入栈
     *   4-2否则，优先级比栈顶元素高，也将运算符压入s1
     *   4-3否则，将s1栈顶的运算符弹出并压入s2，再次转到（4-1）与s1中新的栈顶运算符相比较
     * 5遇到括号时：
     *   5-1如果时左括号，则直接压入s1
     *   5-2如果是右括号，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
     * 6重复2-5，直到表达式的最右边
     * 7将s1中剩余的运算符依次弹出并压入s2
     * 8输出s2，就是中缀表达式变换成的后缀表达式
     * */
    public static List<String> parseSuffixExpreesionList(List<String> list){
        //符号栈
        Stack<String> s1 = new Stack<>();
        //使用List<String> 存储中间结果的
        ArrayList<String> s2 = new ArrayList<>();
        for (String item:list) {
            //如果是一个数，直接存储到s2
            if(item.matches("\\d+")){
                //将数添加到s1
                s2.add(item);
            }else if(item.equals("(")){
                //添加符号到s1
                s1.push(item);
            }else if(item.equals(")")){
                while (!s1.peek().equals("(")){
                    s2.add(s1.pop());
                }
                //将(弹出
                s1.pop();
            }else{
                //当item的优先级小于等于栈顶的优先级，将s1栈顶的优先级弹出并加入到s2中
                while (s1.size()!=0&&Operation.getValue(item)<=Operation.getValue(s1.peek())){
                    s2.add(s1.pop());
                }
                //还需要把这个符号压入栈中
                s1.push(item);
            }
        }
        //将s1中剩余的运算符依次压入s2中
        while (s1.size()!=0){
            s2.add(s1.pop());
        }
        return s2;
    }

}


//编写一个类Operation可以返回一个运算符对应的优先级
class Operation{
    private static int ADD=1;
    private static int SUB=1;
    private static int MUL=2;
    private static int DIV=2;

    //返回对应数字的优先级
    public static int getValue(String operation){
        int result=0;
        switch (operation){
            case "+":
                result=ADD;
                break;
            case "-":
                result=SUB;
                break;
            case "*":
                result=MUL;
                break;
            case "/":
                result=DIV;
                break;
        }
        return result;
    }

}